package tree;

import com.sun.corba.se.spi.ior.IdentifiableFactory;

/**
 * 给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
 * 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
 * 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
 * 返回这些数字之和。题目数据保证答案是一个 32 位 整数
 * @author le
 */
public class SumOfRootToLeafBinaryNumbers
{

    public int sumRootToLeaf(TreeNode root) {

        return dfs(root,0);
    }

    /**
     *
     * @param root 树的根节点
     * @param sum 累加的结果和
     * @return
     */
    public static int dfs(TreeNode root, int sum){
        // 当root == null 时 说明已经走到头了
        if (root == null){
            return 0;
        }
        // 计算当前的十进制的值
        sum = sum*2 + root.val;
        // 叶子
        if (root.left == null && root.right == null){
            return sum;
        }
        int left = dfs(root.left,sum);
        int right = dfs(root.right,sum);
        return left+right;
    }
}
